package com.code.leetcode.offer;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author codeDorado
 * @version 1.0
 * @date 2020/8/6 11:26
 *  此题为 剑指 offer 的 59-2
 */
public class MaxQueue {

    Deque<Integer> deque;
    Deque<Integer> maxDeque;
    public MaxQueue() {
        deque = new LinkedList<>();
        maxDeque = new LinkedList<>();
    }

    public int max_value() {
        return maxDeque.isEmpty() ? -1 : maxDeque.peekFirst();
    }

    public void push_back(int value) {
        deque.addLast(value);
        while (!maxDeque.isEmpty() && maxDeque.peekLast() < value) {
            maxDeque.removeLast();
        }
        maxDeque.addLast(value);
    }

    public int pop_front() {
        Integer first = deque.pollFirst();
        if (first != null && maxDeque.peekFirst().equals(first))
            maxDeque.removeFirst();
        return first == null ? -1 : first;
    }
}
